package leetcode.每日一题.二分查找;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2023/1/4 10:07 PM
 * @description：
 */
public class 有界数组中指定下标处的最大值 {
    @Test
    public void test() {

    }

    class Solution {
        public int maxValue(int n, int index, int maxSum) {
            int left = 1;
            int right = maxSum;
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (valid(mid, n, index, maxSum)) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }

        private boolean valid(int mid, int n, int index, int maxSum) {
            int left = index;
            int right = n - 1 - index;
            return mid + cal(mid, left) + cal(mid, right) <= maxSum;
        }

        private long cal(int big, int length) {
            if (length + 1 < big) {
                int small = big - length;
                return (long) (big - 1 + small) * length / 2;
            } else {
                int ones = length - (big - 1);
                return (long) big * (big - 1) / 2 + ones;
            }
        }
    }
}
